package 排序;

import java.util.Arrays;

// 归并排序
public class MergeSort {
	public static void main(String[] args) {
		int[] arr = {8,4,5,7,1,3,6,2};
		int[] temp = new int[arr.length];
		mergeSort(arr, 0, arr.length-1, temp);
		
		System.out.println(Arrays.toString(arr));
		
	}
	
	public static void mergeSort(int[] arr, int left, int right, int[] temp) {
		if(left < right) {
			int mid = (left + right) >> 1;
			mergeSort(arr, left, mid, temp);
			mergeSort(arr, mid+1, right, temp);
			merge(arr, left, mid, right, temp);
		}
	}
	
	// 合并
	public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
		int i = left;
		int j = mid + 1;
		int t = 0;
		while(i <= mid && j <= right) {
			if(arr[i] <= arr[j]) {
				temp[t] = arr[i];
				i++;
				t++;
			} else {
				temp[t] = arr[j];
				j++;
				t++;
			}
		}
		
		while(i <= mid) {
			temp[t] = arr[i];
			i++;
			t++;
		}
		while(j <= right) {
			temp[t] = arr[j];
			j++;
			t++;
		}
		
		t = 0;
		int k = left;
		while(k <= right) {
			arr[k] = temp[t];
			k++;
			t++;
		}
	}
	
//	public static void mergeSort(int[] arr, int left, int right, int[] temp) {
//		if(left < right) {
//			int mid = (left + right) >> 1;
//			mergeSort(arr, left, mid, temp);
//			mergeSort(arr, mid+1, right, temp);
//			merge(arr, left, mid, right, temp);
//		}	
//	}
//	
//	
//	// 合并
//	public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
//		int i = left;
//		int j = mid + 1;
//		int t = 0;
//		while(i <= mid && j <= right) {
//			if(arr[i] <= arr[j]) {
//				temp[t] = arr[i];
//				i++;
//				t++;
//			} else {
//				temp[t] = arr[j];
//				j++;
//				t++;
//			}
//		}
//		
//		while(i <= mid) {
//			temp[t] = arr[i];
//			i++;
//			t++;
//		}
//		
//		while(j <= right) {
//			temp[t] = arr[j];
//			j++;
//			t++;
//		}
//		
//		t = 0;
//		int k = left;
//		while(k <= right) {
//			arr[k] = temp[t];
//			k++;
//			t++;
//		}
//	}
	
	
//	public static void mergeSort(int[] arr, int left, int right, int[] temp) {
//		if(left < right) {
//			int mid = (left + right)>>1;
//			mergeSort(arr, left, mid, temp);
//			mergeSort(arr, mid+1, right, temp);
//			merge(arr, left, mid, right, temp);
//		}	
//	}
//	
//	// 合并
//	public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
//		int i = left;
//		int j = mid +1;
//		int t = 0;
//		// 1. 拷贝到临时数组
//		while(i <= mid && j <= right) {
//			if(arr[i] <= arr[j]) {
//				temp[t] = arr[i];
//				i++;
//				t++;
//			} else {
//				temp[t] = arr[j];
//				j++;
//				t++;
//			}
//		}
//		
//		// 2. 把剩余的拷贝到临时数组
//		while(i <= mid) {
//			temp[t] = arr[i];
//			i++;
//			t++;
//		}
//		
//		while(j <= right) {
//			temp[t] = arr[j];
//			j++;
//			t++;
//		}
//		
//		// 3. 把temp数组拷贝到arr
//		t = 0;
//		int tempLeft = left;
//		while(tempLeft <= right) {
//			arr[tempLeft] = temp[t];
//			tempLeft++;
//			t++;
//		}
//	}
}
